public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        String s = "a";
        String p = "******a*";
        System.out.println(test.isMatch(s, p));

    }

    public boolean isMatch(String s, String p) {
        /**
         * 通配符匹配
         * 状态表示：
         *  dp[i][j]表示字符串s以i下标为结尾的子字符串 与 p以j下标为结尾的子字符串是否能够完全匹配
         * 状态转移方程：
         *  if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
         *      dp[i][j] = dp[i-1][j-1];
         *  } else {
         *      dp[i][j] = dp[i][j-1] || dp[i-1][j];
         *  }
         * 填表顺序：
         *  从上到下，从左到右
         * 初始化：
         *  由于在填写第一行和第一列时会发生数组越界访问的情况，因此手动赋值
         * 返回值：
         *  return dp[m-1][n-1];
         *
         * 注意事项：
         *  此处的 * 已经明确说明了可以代表空串，但是我们却没有在解题中引入空串的概念，这就是不能解的原因
         *  由此可以得出经验：若是题目中存在空串概念，我们在动规时也应当引入，不然无法进行表示
         * */
        // 1 预处理
        int m = s.length();
        int n = p.length();
        // 2 创建dp表
        boolean[][] dp = new boolean[m+1][n+1];
        // 3 初始化
        dp[0][0] = true;
        for(int k = 1; k <= n; k++) {
            if(p.charAt(k-1) == '*') {
                dp[0][k] = true;
            } else {
                break;
            }
        }
        // 4 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?') {
                    dp[i][j] = dp[i-1][j-1];
                } else if(p.charAt(j-1) == '*') {
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                }
            }
        }
        // 5 返回值
        return dp[m][n];
    }
}
